Planning a supply chain has become a highly complex task in modern industries. A complete supply chain may cover all supply network areas from a supplier's supplier to a customers customer. A complete supply chain may be modelled, for example, from master data such as locations, products, resources, bills of material, etc. and from data representing transport relations.
A resource may be defined, for example, as referring to a machine, person, facility, warehouse, means of transportation or other asset with a limited capacity that fulfils a particular function in the supply chain. A resource's capacity may be defined, for example, by a quantity (e.g., transport or warehouse capacity) or a per-time rate (e.g., production rate per day or week).
A location may be defined, for example, as referring to a place or organizational entity at which quantities of products or resources are managed. Exemplary locations include a production plant, a distribution center, a transportation zone, a stock transfer point, a storage location area, a customer, a vendor (external supplier), a subcontractor, a transportation service provider, a terminal, a geographical area, and a store.
A product may be defined, for example, as referring to a good that is the subject of business activity. A product can be used, consumed or created in the course of a production process. Thus, a product can be any of a raw product, an intermediate product and a final product. A location-product may then be defined by assigning a product to a specific location in a supply chain model. Similarly, a lane-product may be defined by assigning a product to a lane of transportation in a supply chain model.
A bill of material may be defined, for example, as referring to a complete, structured list of the components that make up an object.
Automated supply chain solutions are available in the marketplace and provide various features. For example, SAP AG's presently marketed software solution for planning and controlling the entire supply chain, Advanced Planner and Optimizer (APO), defines production process model (PPM), operation, and activity as further master data. A production process model describes when a plan can be used to manufacture a product. It brings together a bill of material and a work plan or task list and allows to determine at which production facility in what quantity and in what manner a product can be manufactured at a particular time. A production process model will include at least one operation which, in turn, will contain at least one activity. An operation describes an action within a PPM plan and oftentimes consists of numerous activities. An activity thus represents a separate step within an operation. For example, the operation drilling may consist of the following activities: setting up a drill, operating the drill, and tearing down the drill.
It is to be understood that the above-described types of master data are merely exemplary and non-limiting. A person of ordinary skill in the art will readily appreciate that other types of master data are conceivable as well and that the particular application may determine the types of master data to be used.
Supply chain planning frequently involves different types of planning that allow to plan and optimize different aspects of the supply chain. For example, supply network planning may allow to create a plan that describes the product flow along the supply chain so that all the demand requirements can be met. Production planning may allow the planner to create feasible production plans across different production locations to fulfil a demand in time and to the standard expected by the customer. Transportation planning may allow to create a least cost transportation plan while guaranteeing customer service. Other types of planning may exist as well and be implemented in a supply chain planning system.
Supply chain planning problems oftentimes can be formulated as finding a minimum (or maximum) value for an objective function while observing a number of constraints. A typical objective function relates to the overall costs of the production or transportation plan. It can be said that it is a general goal to keep costs as low as possible. Time can also be the subject of an objective function (as, e.g., in the case of having to find a least time consuming plan for transporting goods). Constraints can be imposed, for example, by required safety stocks, the maximum capacity of resources, time requirements, etc.
For finding a solution to a supply chain planning problem, it is a common approach to develop a mathematical representation of the problem and solve the mathematical problem using optimization techniques. A great many of supply chain planning problems can be formulated by a linear objective function and linear equalities or inequalities representing the constraints. Such problems are frequently referred to as linear programming (LP) problems. In practical scenarios, the LP representation of a supply chain planning problem may easily contain several hundred thousand variables or even more than that. If the variables are integer variables, i.e., they can only assume integer values such as a binary value, the problem is called an integer LP problem. In many cases, however, a supply chain planning problem will not only involve integer variables, but variables that may assume non-integer values. The problem is then called a mixed integer linear programming (MILP) problem.
Numerous algorithms have been developed in the art for solving LP problems, including the Simplex algorithm and branch-and-bound and branch-and-cut algorithms for solving MILP problems. All these algorithms are well-known in the art and it is not necessary to elaborate thereon in detail here.
Computation time and computation resources are crucial factors in achieving a optimal solution to a supply chain planning problem. Unfortunately, LP problems and particularly MILP problems are sometimes extremely difficult to solve or even impossible to solve in reasonable computation times. While the number of variables involved in the problem may have an impact on the necessary computation time, it has been found that even comparatively small MILP problems (small referring to the number of variables, for example, less than one hundred) may sometimes be extremely hard to solve.
Usually, there exist several semantically equivalent models for a given problem which are not equally hard to solve. One can therefore attempt to find one of the alternatives that can be solved more easily than other alternatives.
To keep the necessary computation time and computation resources at acceptable levels, however, techniques for preprocessing LP and MILP problems have been developed that allow to transform a given planning problem into one that can be solved more efficiently. Preprocessors are known to employ two main techniques in order to achieve the preprocessing, reformulation and simplification. Reformulation means that some parts of the model are modified or exchanged by others. Reformulation is based on rules. Each rule represents one preprocessing step. By applying a rule to a model, a reformulated model is obtained that one hopes is simpler to solve. Simplification, on the other hand, is a technique that removes redundancy from the problem. Again, simplification relies on rules. Applying a rule results in a simplified model.
A preprocessor applies the different rules as long as they are applicable. The resulting model represents the preprocessed model, which is expected to require less computation time and resources to solve.
It is known to employ preprosessing techniques at the mathematical level, i.e., after a supply chain planning problem described in terms of master data and demands has been converted to a mathematical formulation. The following two articles highlight various techniques for preprocessing zero-one and mixed integer linear programming problems at the mathematical level: Preprocessing and Probing Techniques for Mixed Integer Programming Problems by M. W. P. Savelsbergh, ORSA Journal on Computing, Vol. 6, No. 4, Fall 1994, pp. 445-454; and Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut by Karla L. Hoffman and Manfred Padberg, ORSA Journal on Computing, Vol. 3, No. 2, Spring 1991, pp. 121-134.